//class Solution {
//public:
//    int lenLongestFibSubseq(vector<int>& arr) {
//        int n = arr.size(), ret = 2;
//        vector<vector<int>> dp(n, vector<int>(n, 2));
//        unordered_map<int, int> hash;
//        for (int i = 0; i < n; i++)
//            hash[arr[i]] = i;
//        for (int i = 2; i < n; i++)
//        {
//            for (int j = i - 1; j >= 1; j--)
//            {
//                int x = arr[i] - arr[j];
//                if (hash.count(x) && hash[x] < j)
//                {
//                    dp[i][j] = max(dp[i][j], dp[j][hash[x]] + 1);
//                    ret = max(ret, dp[i][j]);
//                }
//            }
//        }
//        return ret == 2 ? 0 : ret;
//    }
//};




//class Solution {
//public:
//    int longestArithSeqLength(vector<int>& nums) {
//        unordered_map<int, int> hash;
//        hash[nums[0]] = 0;
//        int n = nums.size(), ret = 2;
//        vector<vector<int>> dp(n, vector<int>(n, 2));
//        for (int i = 1; i < n - 1; i++)
//        {
//            for (int j = i + 1; j < n; j++)
//            {
//                int k = 2 * nums[i] - nums[j];
//                if (hash.count(k))
//                {
//                    dp[i][j] = dp[hash[k]][i] + 1;
//                    ret = max(ret, dp[i][j]);
//                }
//            }
//            hash[nums[i]] = i;
//        }
//        return ret;
//    }
//};




class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        unordered_map<long long, vector<long long>> hash;
        for (long long i = 0; i < nums.size(); i++)
            hash[nums[i]].push_back(i);
        int n = nums.size(), ret = 0;
        vector<vector<long long>> dp(n, vector<long long>(n));
        for (int j = 2; j < n; j++)
        {
            for (int i = 1; i < j; i++)
            {
                long long target = (long long)2 * nums[i] - nums[j];
                if (hash.count(target))
                {
                    for (auto k : hash[target])
                    {
                        if (k < i)
                            dp[i][j] += dp[k][i] + 1;
                    }
                }
                ret += dp[i][j];
            }
        }
        return ret;
    }
};